Survivor of the Josephus Problem

The following problem is a famous exercise in programming. It is called the Josephus problem.

There are n persons in a circle. We start with one person, and count to k clockwise. This person is removed from the circle. The process is continued with the next person, until there is only one left. Which one is it?

We solve it first with a simulation. The following function steps k times from i to the right (skipping zeros). Then it removes this element, returning its position.

>function countAndRemove (i,k,v) ...
   loop 1 to k
     repeat
       i=i+1;
       if i>cols(v) then i=1; endif;
       until v[i];
     end;
   end;
   v[i]=0;
   return i;
 endfunction

Test that.

>format(4,0); v=ones(1,10)

  1   1   1   1   1   1   1   1   1   1

>i=0; loop 1 to 9; i=countAndRemove(i,7,v), v, end;

  7 
  1   1   1   1   1   1   0   1   1   1 
  4 
  1   1   1   0   1   1   0   1   1   1 
  2 
  1   0   1   0   1   1   0   1   1   1 
  1 
  0   0   1   0   1   1   0   1   1   1 
  3 
  0   0   0   0   1   1   0   1   1   1 
  6 
  0   0   0   0   1   0   0   1   1   1 
 10 
  0   0   0   0   1   0   0   1   1   0 
  5 
  0   0   0   0   0   0   0   1   1   0 
  8 
  0   0   0   0   0   0   0   0   1   0

That looks okay.

Now we can write a function, which removes n-1 persons, and returns the position of the survivor.

>function map determineSurvivor (k,n) ...
   v=ones(1,n);
   i=0;
   loop 1 to n-1;
     i=countAndRemove(i,k,v);
   end;
   return nonzeros(v)
 endfunction

>determineSurvivor(7,10)

Due to the "map" keyword, we can generate a table for step sizes k, and total numbers n.

>determineSurvivor(1:10,(1:10)')

  1   1   1   1   1   1   1   1   1   1 
  2   1   2   1   2   1   2   1   2   1 
  3   3   2   2   1   1   3   3   2   2 
  4   1   1   2   2   3   2   3   3   4 
  5   3   4   1   2   4   4   1   2   4 
  6   5   1   5   1   4   5   3   5   2 
  7   7   4   2   6   3   5   4   7   5 
  8   1   7   6   3   1   4   4   8   7 
  9   3   1   1   8   7   2   3   8   8 
 10   5   4   5   3   3   9   1   7   8

At that point, we notice, that we are not very efficient.

We could remove just one person, and then evaluate the function for one less person recursively. To get the position of the survivor, we need to add the position we are starting off and take the result modulo n.

>function map posOfSurvivor (k,n) ...
 if n==1 then return 1; endif;
 res=mod(k+posOfSurvivor(k,n-1),n);
 if res==0 then return n;
 else return res;
 endif;
 endfunction

>posOfSurvivor(1:10,(1:10)')

  1   1   1   1   1   1   1   1   1   1 
  2   1   2   1   2   1   2   1   2   1 
  3   3   2   2   1   1   3   3   2   2 
  4   1   1   2   2   3   2   3   3   4 
  5   3   4   1   2   4   4   1   2   4 
  6   5   1   5   1   4   5   3   5   2 
  7   7   4   2   6   3   5   4   7   5 
  8   1   7   6   3   1   4   4   8   7 
  9   3   1   1   8   7   2   3   8   8 
 10   5   4   5   3   3   9   1   7   8

Josephus Problem

The Josephus problem is a bit more complicated, since it asks for the position of the last two remaining persons. But we can write a function for this too.

>function determineLastTwoSurvivors (k,n) ...
   v=ones(1,n);
   i=0;
   loop 1 to n-2;
     i=countAndRemove(i,k,v);
   end;
   return nonzeros(v)
 endfunction

>shortformat; determineLastTwoSurvivors(3,40)

[13,  28]

Examples